Parameterized Complexity

Parameterized Complexity (Spring 2019++)

Course Description: The course will focus on the parameterized algorithms and complexity. Over the past thirty years, the field has become extremely vibrant and one of the go to field to deal with NP-hardness. The idea of this page is to make a comprehensive video/lecture notes library of the field. The page will be updated as and when new methodology and techniques get developed.

Textbooks: There is no course text for new materials. However, most of the material we cover can be found in the following text books.

• Kernelization: Theory of Parameterized Preprocessing (with F. V. Fomin, D. Lokshtanov, and M. Zehavi). Cambridge University of Press, 2019, ISBN: 9781107415157, https://doi.org/10.1017/9781107415157
• Parameterized Algorithms (with M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuck and M. Pilipczuck). Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555.

Prerequisites: Mathematical maturity and comfort with undergraduate algorithms and basic probability.

Lectures :

1. Lecture 00: Introduction to Parameterized Algorithms [Video]
2. Lecture 01: Kernalization 1: High Degree+Greedy [Video]
3. Lecture 02: Kernelization 2: Sunflower Lemma [Video]
4. Lecture 03: Kernelization 3: Sunflower Lemma + Dominating set in kij free graphs [Video]
5. Lecture 04: Kernelization 4: Matching Based Kernels [Video]
6. Lecture 05: Kernelization 5: Generalized Matching (Expansion Lemma) [Video]
7. Lecture 06: Branching 1: Simple Examples [Video]
8. Lecture 07: Branching 2: Branching with non-trivial measure [Video]
9. Lecture 08: Branching 3: Branching with non-trivial measure [Video]
10. Lecture 09: Branching 4: Vertex cover above LP [Video]
11. Lecture 10: Randomization in Parameterized Algorithms [Video]
12. Lecture 11: Iterative Compression and Iterative Localization [Video]
13. Lecture 12: Important Separators 1 [Video]
14. Lecture 13: Important Separators 2 [Video]
15. Lecture 14: Important Separators 3 [Video]
16. Lecture 15: Matroids 1: Basics [Video]
17. Lecture 16: Matroids 2: Representation and Representative Families [Video]
18. Lecture 17: Matroids 3: Algorithms to compute Representative families and its Applications [Video]
19. Lecture 18: Matroids 4: Representative families Applications and Computation of Representative Families on General Matroids [Video]
20. Lecture 19: Parameterized Intractability 1 [Video]
21. Lecture 20: Parameterized Intractability 2 [Video]
22. Lecture 21: Parameterized Intractability 3 [Video]
23. Lecture 22: Paths, Trees and t-Decomposable Graphs [Video]
24. Lecture 23: Towards Defining Tree - Decomposable Graphs [Video]
25. Lecture 24: Tree -Decomposition and t-decomposability and relation to tree-width [Video]
26. Lecture 25: Structural Properties of Tree-Decomposition [Video]
27. Lecture 26: Algorithm to compute a constant factor tree decomposition [Video]
28. Lecture 27: Dynamic Programming Algorithms over graphs of treewidth t [Video]
29. Lecture 28: Courcelle's theorem and Planar-F-Deletion via Protrusion Decomposition [Video]
30. Lecture 29: Protrusion Decomposition, Bidimensionability and Kernels on Planar graphs [Video]
31. Lecture 30: Sub-exponential Parameterized Algorithms [Video]
32. Lecture 31: Biclique Hardness -- 1 [Video]
33. Lecture 32: Biclique Hardness -- 2 [Video]
34. Lecture 33: Biclique Hardness -- 3 [Video]
35. Lecture 34: Lossy Kernelization (Cycle Packing) -- 1 [Video]
36. Lecture 35: Lossy Kernelization (Cycle Packing) -- 2 [Video]
37. Lecture 36: Lossy Kernelization (Cycle Packing) -- 3 [Video]
38. Lecture 37: Lossy Kernelization (Cycle Packing) -- 4 [Video]
39. Lecture 38: Monotone Local Search -- 1 [Video]
40. Lecture 39: Monotone Local Search -- 2 [Video]
41. Lecture 40: Monotone Local Search -- 3 [Video]

Video Lectures from 2017 version of the course could be found at [Video]